import java.io._
import scala.util.parsing.combinator._
class SL2Type
case class SL2Int() extends SL2Type
case class SL2Bool() extends SL2Type
case class SL2Fun(paramTypes : List[SL2Type], returnType : SL2Type) extends SL2Type
class Expr
class Definition
case class Block(defs : List[Definition], expr : Expr)
case class Number(value : Int) extends Expr
case class Variable(name : String) extends Expr
case class Factorial(value : Expr) extends Expr
case class Operator(left : Expr, right : Expr,f: (Int, Int) => Int) extends Expr
case class BoolOp(left : Expr, right : Expr,f: (Int, Int) => Boolean) extends Expr
case class Equals(left : Expr, right : Expr) extends Expr
case class NotEquals(left : Expr, right : Expr) extends Expr
case class Function(params : List[(TypedIdent)], body : Block) extends Expr
case class IfExpr(cond : Expr, thenBlock : Block, elseBlock : Block) extends Expr
case class Funcall(fun : Expr, args : List[Expr]) extends Expr
case class TypedIdent(name : String, type2 : SL2Type)
// Note: Closure instances are produced in eval, not the parser itself
case class Closure(params : List[String], body : Block, var env : List[TypedIdent]) {
 override def toString = "Closure(" + params + "," + body + ")"
}

case class Valdef(name : String, expr : Expr) extends Definition
case class Defdef(typedName : TypedIdent, fun : Function) extends Definition
// The parser has changed to take types of variables and parameters
class SL2Parser extends JavaTokenParsers {
	def block: Parser[Block] = rep(valdef | defdef) ~ expr ^^ { case lst ~ e => Block(lst, e) }
	def expr: Parser[Expr] = ("if" ~> ("(" ~> expr <~ ")") ~ block <~ "else") ~ block ^^ {
		case e ~ b1 ~ b2 => IfExpr(e, b1, b2)
	} | expr2
	def expr2: Parser[Expr] = (expr3 ~ rep(("==" | "!=") ~ expr3)) ^^ {
		case a ~ lst => (a /: lst) {
			case (x, "==" ~ y) => Equals(x, y)
			case (x, "!=" ~ y) => NotEquals(x, y)
		}
	}
	def expr3: Parser[Expr] = (expr4 ~ rep(("<" | "<=" | ">" | ">=" ) ~ expr4)) ^^ {
		case a ~ lst => (a /: lst) {
			case (x, "<" ~ y) => BoolOp(x, y, _ < _)
			case (x, "<=" ~ y) => BoolOp(x, y, _ <= _)
			case (x, ">" ~ y) => BoolOp(x, y, _ > _)
			case (x, ">=" ~ y) => BoolOp(x, y, _ >= _)
		}
	}

	def expr4: Parser[Expr] = (term ~ rep(("+" | "-") ~ term)) ^^ {
		case a ~ lst => (a /: lst) {
			case (x, "+" ~ y) => Operator(x, y, _ + _)
			case (x, "-" ~ y) => Operator(x, y, _ - _)
		}
	}
	def term: Parser[Expr] = (factor ~ rep(("*" | "/" ) ~ factor)) ^^ {
		case a ~ lst => (a /: lst) {
			case (x, "*" ~ y) => Operator(x, y, _ * _)
			case (x, "/" ~ y) => Operator(x, y, _ / _)
		}
	}
	def factor: Parser[Expr] =operator<~"!" ^^{ case a => new Factorial(a) }|operator
	def operator: Parser[Expr] = wholeNumber ^^ { x : String => Number(x.toInt) } |"(" ~> expr <~ ")" | valOrFuncall
	def valOrFuncall = valOrFun ~ opt( "(" ~> repsep(expr, ",") <~ ")" ) ^^ {
		case expr ~ Some(args) => Funcall(expr, args)
		case expr ~ None => expr
	}
	def valOrFun = "(" ~> expr <~ ")" |ident ^^ { Variable(_) } |funliteral
	def funliteral: Parser[Function] = ("{" ~> repsep(typedIdent, ",") <~ "=>") ~ block <~ "}" ^^ {
		case params ~ block => Function(params, block)
	}
	def typeSpec : Parser[SL2Type] = "Int" ^^ { x : String => SL2Int() } |
									"Bool" ^^ { x : String => SL2Bool() } |
									("(" ~> repsep(typeSpec, ",") <~ ")") ~ ("=>" ~> typeSpec) ^^ {
									case paramTypes ~ returnType => SL2Fun(paramTypes, returnType)
	}
	def typedIdent : Parser[TypedIdent] = (ident <~ ":") ~ typeSpec ^^ {
	  case id ~ ty => new TypedIdent (id, ty)
	}
	
	def funcall: Parser[Expr] = expr ~ ( "(" ~> repsep(expr, ",") <~ ")" ) ^^ {
	case fun ~ args => Funcall(fun, args)
	}

	def valdef: Parser[Definition] = ("val" ~> ident <~ "=") ~ (expr <~ ";") ^^ {
	case name ~ expr => Valdef(name, expr)
	}
	def defdef: Parser[Definition] = ("def" ~> typedIdent <~ "=") ~ (funliteral <~ ";") ^^ {
	case name ~ expr => Defdef(name, expr)
	}
	
}
import java.io._
import scala.util.parsing.combinator._
object main {
	def spy[T](t : T) = { println(t); t }
	def lookup[SL2type](name : String, symbols : List[TypedIdent]) =
		symbols.find(_.name == name) match {
		case Some(pair) => pair.type2
	}
	def typeof(expr : Expr, types : List[TypedIdent]) : SL2Type =
		expr match {
			case Number(_) => SL2Int()
			case Variable(name) => lookup(name, types)
			case Operator(left, right, _) => {
					assert(typeof(left, types) == SL2Int())
					assert(typeof(right, types) == SL2Int())
					SL2Int()
			}
			case BoolOp(left, right, _) => {
				assert(typeof(left, types) == SL2Int())
				assert(typeof(right, types) == SL2Int())
				SL2Bool()
			}
			case Equals(_, _) => SL2Bool()
			case NotEquals(_, _) => SL2Bool()
			case IfExpr(cond, block1, block2) => {
				assert(typeof(cond, types) == SL2Bool())
				val blocktype = typeofBlock(block1, types)
				assert(blocktype == typeofBlock(block2, types))
				blocktype
			}
			case Function(params, body) => SL2Fun(params.map({_.type2}), typeofBlock(body, params ::: types))
			case Funcall(expr, args) => {
				val exprType = typeof(expr, types)
				exprType match {
					case fun : SL2Fun => {
					// assert fun params match types of args
					assert(fun.paramTypes.size == args.size)
					assert(fun.paramTypes.zip(args).forall(scala.Function.tupled {
					_ == typeof(_, types) }))
					fun.returnType
					}
				}
			}
		}
	//case class Block(defs : List[Definition], expr : Expr)
	def typeofBlock(block : Block, symbols : List[(TypedIdent)]) : SL2Type = {
		typeof(block.expr, (symbols /: block.defs) {typeofDef(_ , _) } )
		//kt type cua tung def trong block va them vao List types
	}
	//case class Valdef(name : String, expr : Expr) extends Definition
	//case class Defdef(typedName : (String, SL2Type), fun : Function) extends Definition
	//case class Function(params : List[(TypedIdent)], body : Block) extends Expr
	//case class Block(defs : List[Definition], expr : Expr)
	def typeofDef(types : List[(TypedIdent)], defn : Definition) : List[(TypedIdent)] = defn match {
		case Valdef(name, expr) => { TypedIdent(name, typeof(expr, types)) :: types }
		case Defdef(typedName, fun) => {
			val retType = typedName.type2 //return type
			//fun.params.map(_.type2): cac type cua param
			//case class SL2Fun(paramTypes : List[SL2Type], returnType : SL2Type) extends SL2Type
			val funType = SL2Fun(fun.params.map(_.type2), retType)
			val newTypes = TypedIdent(typedName.name,funType) :: types
			typeof(fun, newTypes) match {
				case funType2 : SL2Fun => assert(funType2.returnType == retType)
			}
			newTypes
		}
	}
	
// The functions below do evaluation in the usual way
	def eval(expr : Expr, symbols : List[TypedIdent]) : Any =expr match {
		case Number(num) => num
		case Variable(name) => lookup(name, symbols)
		case Factorial(ex) => { val x = eval(ex,symbols).toString().toInt
		  if(x <= 0) 1
		  else eval(Operator(Number(x),Factorial(Number(x-1)),_*_),symbols)
		  
		}
		case Operator(left, right, f) => {
			eval(left, symbols) match {
				case arg1 : Int =>
				eval(right, symbols) match {
					case arg2 : Int =>
					f(arg1, arg2)
				}
			}
		}
		case BoolOp(left, right, f) => {
			eval(left, symbols) match {
			case arg1 : Int =>
			eval(right, symbols) match {
				case arg2 : Int =>
				f(arg1, arg2)
				}
			}
		}
		case Equals(left, right) => eval(left, symbols) == eval(right, symbols)
		case NotEquals(left, right) => eval(left, symbols) != eval(right, symbols)
		case IfExpr(cond, block1, block2) => {
			eval(cond, symbols) match {
			case result : Boolean =>
				if (result) evalBlock(block1, symbols) else evalBlock(block2, symbols)
			}
		}
		//case class Funcall(fun : Expr, args : List[Expr]) extends Expr
		case Funcall(fun, args) => eval(fun, symbols) match {
			case Closure(params, body, syms) =>
			//evalBlock(body, params.zip(args.map(eval(_, symbols))) ::: syms)
			evalBlock(body, params.toList.map( x => TypedIdent(x,lookup(x,syms))) ::: syms)
		}
		case Function(params, body) => Closure(params.map(_.name), body, symbols)
		case _ => expr
	}
	def evalDef(symbols : List[TypedIdent], defn : Definition) = defn match {
		case Defdef(name, Function(params, body)) => {
			val cl = Closure(params.map(_.name), body, symbols)
			val syms = TypedIdent(name.name, lookup(name.name,symbols)) :: symbols
			cl.env = syms
			syms
		}
		case Valdef(name, Function(params, body)) => { TypedIdent(name, lookup(name,symbols)) :: symbols }
		case Valdef(name, expr) => { TypedIdent(name, typeof(expr, symbols)) :: symbols }
	}
	def evalBlock(block : Block, symbols : List[TypedIdent]) : Any = {
		eval(block.expr, (symbols /: block.defs) {evalDef(_ , _) } )
	}
	def main(args : Array[String]) : Unit = {
		val parser = new SL2Parser
		val result = parser.parse(parser.block, new InputStreamReader(System.in))
		println(result)
		println(typeofBlock(result.get, List()))
		println(evalBlock(result.get, List()))
	}
}
